//===--- ARCRegionState.h ---------------------------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#ifndef POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_ARCREGIONSTATE_H
#define POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_ARCREGIONSTATE_H

#include "polarphp/pil/optimizer/internal/arc/GlobalLoopARCSequenceDataflow.h"
#include "polarphp/basic/NullablePtr.h"

namespace polar {

class LoopRegion;
class LoopRegionFunctionInfo;
class AliasAnalysis;
class RCIdentityFunctionInfo;

/// Per-Region state.
class ARCRegionState {
public:
   // TODO: These are relatively expensive, find something else to use here.
   using TopDownMapTy = SmallBlotMapVector<PILValue, TopDownRefCountState, 4>;
   using BottomUpMapTy = SmallBlotMapVector<PILValue, BottomUpRefCountState, 4>;

private:
   /// The region that this ARCRegionState summarizes information for.
   ///
   /// The only time that the pointer is null is during initialization. Using
   /// NullablePtr is just a convenient way to make sure that we assert if we
   /// attempt to use Region during initialization before the pointer is set.
   NullablePtr<LoopRegion> Region;

   /// The top-down traversal uses this to record information known about a
   /// pointer at the bottom of each block.
   TopDownMapTy PtrToTopDownState;

   /// The bottom-up traversal uses this to record information known about a
   /// pointer at the top of each block.
   BottomUpMapTy PtrToBottomUpState;

   /// Is this a region from which we can leak ARC values?
   ///
   /// If we know that the program has entered a state from which it is
   /// guaranteed to terminate soon, in our model we allow for all memory to be
   /// leaked since the operating system will soon reclaim the memory. We take
   /// advantage of this to ignore control flow.
   bool AllowsLeaks;

   /// A list of instructions contained in this region that can either use or
   /// decrement reference counts.
   ///
   /// This is flow insensitive since we just add all of the potential
   /// users/decrements in subregions without caring if there is only one along a
   /// path. This is for simplicity in the first iteration.
   ///
   /// TODO: This needs a better name.
   llvm::SmallVector<PILInstruction *, 4> SummarizedInterestingInsts;

public:
   ARCRegionState(LoopRegion *R, bool AllowsLeaks);

   /// Is this Region from which we can leak memory safely?
   bool allowsLeaks() const { return AllowsLeaks; }

   /// Return the region associated with this ARCRegionState.
   ///
   /// Even though Region is a NullablePtr, it is only null during
   /// initialization. This method should not be called then.
   const LoopRegion *getRegion() const { return Region.get(); }
   LoopRegion *getRegion() { return Region.get(); }

   /// Top Down Iterators
   using topdown_iterator = TopDownMapTy::iterator;
   using topdown_const_iterator = TopDownMapTy::const_iterator;
   topdown_iterator topdown_begin() { return PtrToTopDownState.begin(); }
   topdown_iterator topdown_end() { return PtrToTopDownState.end(); }
   topdown_const_iterator topdown_begin() const {
      return PtrToTopDownState.begin();
   }
   topdown_const_iterator topdown_end() const { return PtrToTopDownState.end(); }
   iterator_range<topdown_iterator> getTopDownStates() {
      return make_range(topdown_begin(), topdown_end());
   }

   /// Bottom up iteration.
   using bottomup_iterator = BottomUpMapTy::iterator;
   using bottomup_const_iterator = BottomUpMapTy::const_iterator;
   bottomup_iterator bottomup_begin() { return PtrToBottomUpState.begin(); }
   bottomup_iterator bottomup_end() { return PtrToBottomUpState.end(); }
   bottomup_const_iterator bottomup_begin() const {
      return PtrToBottomUpState.begin();
   }
   bottomup_const_iterator bottomup_end() const {
      return PtrToBottomUpState.end();
   }
   iterator_range<bottomup_iterator> getBottomupStates() {
      return make_range(bottomup_begin(), bottomup_end());
   }

   /// Attempt to find the PtrState object describing the top down state for
   /// pointer Arg. Return a new initialized PtrState describing the top down
   /// state for Arg if we do not find one.
   TopDownRefCountState &getTopDownRefCountState(PILValue Ptr) {
      return PtrToTopDownState[Ptr];
   }

   /// Attempt to find the PtrState object describing the bottom up state for
   /// pointer Arg. Return a new initialized PtrState describing the bottom up
   /// state for Arg if we do not find one.
   BottomUpRefCountState &getBottomUpRefCountState(PILValue Ptr) {
      return PtrToBottomUpState[Ptr];
   }

   /// Blot \p Ptr.
   void clearBottomUpRefCountState(PILValue Ptr) {
      PtrToBottomUpState.erase(Ptr);
   }

   /// Blot \p Ptr.
   void clearTopDownRefCountState(PILValue Ptr) { PtrToTopDownState.erase(Ptr); }

   void clearTopDownState() { PtrToTopDownState.clear(); }
   void clearBottomUpState() { PtrToBottomUpState.clear(); }

   /// Clear both the bottom up *AND* top down state.
   void clear() {
      clearTopDownState();
      clearBottomUpState();
   }

   using const_reverse_summarizedinterestinginsts_iterator =
   decltype(SummarizedInterestingInsts)::const_reverse_iterator;
   const_reverse_summarizedinterestinginsts_iterator
   summarizedinterestinginsts_rbegin() const {
      return SummarizedInterestingInsts.rbegin();
   }
   const_reverse_summarizedinterestinginsts_iterator
   summarizedinterestinginsts_rend() const {
      return SummarizedInterestingInsts.rend();
   }

   using const_summarizedinterestinginsts_iterator =
   decltype(SummarizedInterestingInsts)::const_iterator;
   const_summarizedinterestinginsts_iterator
   summarizedinterestinginsts_begin() const {
      return SummarizedInterestingInsts.begin();
   }
   const_summarizedinterestinginsts_iterator
   summarizedinterestinginsts_end() const {
      return SummarizedInterestingInsts.end();
   }
   iterator_range<const_summarizedinterestinginsts_iterator>
   getSummarizedInterestingInsts() const {
      return {summarizedinterestinginsts_begin(),
              summarizedinterestinginsts_end()};
   }

   /// Merge in the state of the successor basic block. This is currently a stub.
   void mergeSuccBottomUp(ARCRegionState &SuccRegion);

   /// Initialize this Region with the state of the successor basic block. This
   /// is
   /// called on a basic block's state and then any other successors states are
   /// merged in. This is currently a stub.
   void initSuccBottomUp(ARCRegionState &SuccRegion);

   /// Merge in the state of the predecessor basic block. This is currently a
   /// stub.
   void mergePredTopDown(ARCRegionState &PredRegion);

   /// Initialize the state for this Region with the state of its predecessor
   /// Region. Used to create an initial state before we merge in other
   /// predecessors. This is currently a stub.
   void initPredTopDown(ARCRegionState &PredRegion);

   /// If this region is a block, process all instructions top down. Otherwise,
   /// apply the summarized top down information to the merged top down
   /// state. Returns true if nested retains were detected while visiting
   /// instructions. Returns false otherwise.
   bool processTopDown(
      AliasAnalysis *AA, RCIdentityFunctionInfo *RCIA,
      LoopRegionFunctionInfo *LRFI,
      BlotMapVector<PILInstruction *, TopDownRefCountState> &DecToIncStateMap,
      llvm::DenseMap<const LoopRegion *, ARCRegionState *> &LoopRegionState,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);

   /// If this region is a block, process all instructions bottom up. Otherwise,
   /// apply the summarized bottom up information to the merged bottom up
   /// state. Returns true if nested releases were detected while visiting
   /// instructions. Returns false otherwise.
   bool processBottomUp(
      AliasAnalysis *AA, RCIdentityFunctionInfo *RCIA,
      EpilogueARCFunctionInfo *EAFI, LoopRegionFunctionInfo *LRFI,
      bool FreezeOwnedArgEpilogueReleases,
      BlotMapVector<PILInstruction *, BottomUpRefCountState> &IncToDecStateMap,
      llvm::DenseMap<const LoopRegion *, ARCRegionState *> &RegionStateInfo,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);

   void summarizeBlock(PILBasicBlock *BB);

   void summarize(
      LoopRegionFunctionInfo *LRFI,
      llvm::DenseMap<const LoopRegion *, ARCRegionState *> &RegionStateInfo);

   /// Add \p I to the interesting instruction list of this region if it is a
   /// block. We assume that I is an instruction in the block.
   void addInterestingInst(PILInstruction *I);

   /// Remove \p I from the interesting instruction list of this region if it is
   /// a block. We assume that I is an instruction in the block.
   void removeInterestingInst(PILInstruction *I);

private:
   void processBlockBottomUpPredTerminators(
      const LoopRegion *R, AliasAnalysis *AA, LoopRegionFunctionInfo *LRFI,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);
   bool processBlockBottomUp(
      const LoopRegion *R, AliasAnalysis *AA, RCIdentityFunctionInfo *RCIA,
      EpilogueARCFunctionInfo *EAFI,
      LoopRegionFunctionInfo *LRFI, bool FreezeOwnedArgEpilogueReleases,
      BlotMapVector<PILInstruction *, BottomUpRefCountState> &IncToDecStateMap,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);
   bool processLoopBottomUp(
      const LoopRegion *R, AliasAnalysis *AA, LoopRegionFunctionInfo *LRFI,
      llvm::DenseMap<const LoopRegion *, ARCRegionState *> &RegionStateInfo,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);

   bool processBlockTopDown(
      PILBasicBlock &BB, AliasAnalysis *AA, RCIdentityFunctionInfo *RCIA,
      BlotMapVector<PILInstruction *, TopDownRefCountState> &DecToIncStateMap,
      ImmutablePointerSetFactory<PILInstruction> &SetFactory);
   bool
   processLoopTopDown(const LoopRegion *R, ARCRegionState *State,
                      AliasAnalysis *AA, LoopRegionFunctionInfo *LRFI,
                      ImmutablePointerSetFactory<PILInstruction> &SetFactory);

   void summarizeLoop(
      const LoopRegion *R, LoopRegionFunctionInfo *LRFI,
      llvm::DenseMap<const LoopRegion *, ARCRegionState *> &RegionStateInfo);
};

} // end polar namespace

#endif // POLARPHP_PIL_OPTIMIZER_INTERNAL_ARC_ARCREGIONSTATE_H
